/*
    TSPClasses - Utility classes for the travelling salesman problem
    Copyright (C) 2011  Laurent Poirrier

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef TSP_CLASSES_HPP
#define TSP_CLASSES_HPP
#include <vector>
#include <list>
#include <algorithm>

// **************************************************************************
// Parameters
// **************************************************************************
#define TSP_DEFAULT_INT_TOL	1e-6


// **************************************************************************
// Global class declarations
// **************************************************************************
template<typename T>
class EdgeData {

public:
	EdgeData();
	EdgeData(int nVertices);
	EdgeData(const EdgeData &src);
	~EdgeData();
	
	EdgeData<T> &operator=(const EdgeData &src);
	
	void clear();
	
	void resize(int nVertices);
	int  vertices() const;
	int  edges() const;
	int  offset(int i, int j) const;
	T   &array(int offs = 0);
	const T &array(int offs = 0) const;

	void set(T v);
	void set(int i, int j, T v);
	T    get(int i, int j) const;
	
	T   &operator() (int i, int j);
	T    operator*(const EdgeData &src) const;

private:
	int n;
	std::vector<T> values;

};


// **************************************************************************
// TSPModel
// **************************************************************************
class TSPModel : public EdgeData<double> {

public:
	TSPModel();
	TSPModel(int nVertices);
	TSPModel(const EdgeData<double> &src);
	TSPModel(const TSPModel &src);
	~TSPModel();

	TSPModel &operator=(const EdgeData<double> &src);
	TSPModel &operator=(const TSPModel &src);
};

// **************************************************************************
// TSPSolution
// **************************************************************************
class TSPSolution : public EdgeData<double> {

public:
	TSPSolution();
	TSPSolution(int nVertices);
	TSPSolution(const EdgeData<double> &sol);
	TSPSolution(const TSPSolution &sol);
	~TSPSolution();
	
	TSPSolution &operator=(const EdgeData<double> &sol);
	TSPSolution &operator=(const TSPSolution &sol);

	double getCost(const TSPModel &model) const;
	
	bool   isIntegral(double tol = TSP_DEFAULT_INT_TOL) const;
	bool   isIntegral(int i, int j, double tol = TSP_DEFAULT_INT_TOL) const;

	void   setFeasible(bool yes = true);
	bool   isFeasible() const;
	
private:
	bool feasible;

};

// **************************************************************************
// TSPFixing
// **************************************************************************
class TSPFixing : public EdgeData<char> {

public:
	TSPFixing();
	TSPFixing(int nVertices);
	TSPFixing(const TSPFixing &src);
	~TSPFixing();
	
	TSPFixing &operator=(const EdgeData<char> &src);
	TSPFixing &operator=(const TSPFixing &src);

	void unfix();

	void fix(int i, int j, bool value);
	void fix(int i, int j, double value);
	void unfix(int i, int j);
	
	bool empty() const;
	bool isFixed(int i, int j) const;
	double fixedValue(int i, int j) const;

};

// **************************************************************************
// TSPCut
// **************************************************************************
class TSPCut : public EdgeData<double> {

public:

	TSPCut();
	TSPCut(int nVertices);
	TSPCut(const TSPCut &cut);
	~TSPCut();  
	
	TSPCut &operator=(const EdgeData<double> &src);
	TSPCut &operator=(const TSPCut &src);

	// 'E' :  = (Equal)
	// 'G' : >= (Greater or equal)
	// 'L' : <= (Less or equal)
	void   setSense(char cutSense);
	char   getSense() const;
	
	void   setRHS(double rightHandSide);
	double getRHS() const;
	
	// slack >= 0 : verified
	double slack(const TSPSolution &sol) const;

private:
	char sense;
	double rhs;

};

// **************************************************************************
// TSPCutPool
// **************************************************************************
typedef std::list<TSPCut> TSPCutPool;


#endif

